package leetcode.p877;

/**
 * @author: trtan
 * @date: 2021-06-16 14:04
 **/
public class StoneGame {
    /**
     * 首先石子堆数为偶数堆，设A为先手，B为后手
     * 每次取一堆，那么最后剩一堆B取，这样就成了从某个位置i开始取，不断取i-1或i+1的位置取石子堆。
     * 设dp[i][j]代表A、B在区间[i，j]取石子差值最大是多少。
     * 那么i>j时，状态不存在，故dp[i][j] = 0
     * i == j时，只能取piles[i]，另一个玩家还没取，故dp[i][j] = piles[i];
     * i < j时，那么就分为这个玩家取的是i还是j，dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
     * 遍历顺序： 考虑到i由i+1转移，j由j-1转移，故i从大到小遍历，j从小到大遍历
     * 最终dp[0][len-1]即为A、B在区间[0,len-1]取石子差值最大是多少
     * 如果最终大于0，说明A赢，小于0说明B赢
     * @param piles
     * @return boolean
     * @author trtan
     * @date 2021/6/16 14:06
     */
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] > 0 ? true : false;
    }

    /**
     * 另一个解法
     * 由于n个数可以分为奇数位置上的和和偶数位置上的和(这里下标从0开始)
     * 而题目也保证两个和肯定不相等，那么先手知道了全选奇数位置和更大还是全选偶数位置和更大
     * 先手每次可以保证给对手只存在奇数或者偶数位置上的数，
     * 比如先手要全部奇数位置上的数，那么先手就选最后一个位置上的数，后手就只能从0或n-2中选择一个，接着依旧会出现奇偶两个位置
     * 同理，先手要偶数位置上的数也是一样的做法。
     * 最终结果就是先手必胜
     * @param piles
     * @return boolean
     * @author trtan
     * @date 2021/6/16 14:38
     */
    public boolean stoneGame2(int[] piles) {
        return true;
    }
}
